package leetcode

// https://leetcode.cn/problems/implement-trie-prefix-tree/description/

type TrieByMap struct {
	path    map[int32]*TrieByMap
	passNum int
	endNum  int
}

func Constructor() TrieByMap {
	return TrieByMap{make(map[int32]*TrieByMap), 0, 0}
}

func (root *TrieByMap) Insert(word string) {
	cur := root
	for _, c := range word {
		if _, ok := cur.path[c]; !ok {
			cur.path[c] = &TrieByMap{make(map[int32]*TrieByMap), 0, 0}
		}
		cur = cur.path[c]
		cur.passNum++
	}
	cur.endNum++
}

func (root *TrieByMap) Search(word string) bool {
	cur := root
	for _, c := range word {
		if _, ok := cur.path[c]; !ok {
			return false
		}
		cur = cur.path[c]
	}
	return cur.endNum > 0
}

func (root *TrieByMap) StartsWith(prefix string) bool {
	cur := root
	for _, c := range prefix {
		if _, ok := cur.path[c]; !ok {
			return false
		}
		cur = cur.path[c]
	}
	return cur.passNum > 0
}

// Erase 从Trie树中删除一个字符串。
// 如果该字符串存在于树中，则减少与该字符串相关的计数，并从树中移除该字符串。
// 参数:
//
//	s - 要删除的字符串。
//
// 该方法不返回值。
func (root *TrieByMap) Erase(s string) {
	// 检查字符串是否存在于树中。
	if root.Search(s) {
		// 减少根节点的通过次数，因为我们要删除一个字符串。
		root.passNum--
		// 开始从根节点遍历树。
		cur := root
		// 遍历字符串的每个字符。
		for _, cha := range s {
			// 获取当前字符对应的节点。
			next := cur.path[cha]
			// 减少当前节点的通过次数。
			next.passNum--
			// 如果通过次数为0，表示没有其他字符串经过这个节点，删除它，释放当前节点以及后续节点的内存。
			if next.passNum == 0 {
				// 从当前节点的路径中删除该字符的节点。
				delete(cur.path, cha)
				// 结束删除操作。
				return
			} else {
				// 否则，继续沿着路径向下遍历。
				cur = next
			}
		}
		// 减少结束节点的结束次数，表示一个字符串的结束。
		cur.endNum--
	}
}

/**
 * Your TrieByMap object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(word);
 * param_2 := obj.Search(word);
 * param_3 := obj.StartsWith(prefix);
 */
